package algorithm

import (
	"fmt"
)

func swap(a int, b int) (int, int) {
	return b, a
}
func partition(ss []int, begin, end int) int {
	val := ss[begin]
	i, j := begin, begin+1
	for j < end {
		if ss[j] < val {
			i++
			ss[i], ss[j] = swap(ss[i], ss[j])
		}
		j++
	}
	ss[i], ss[begin] = swap(ss[i], ss[begin])
	return i
}
func quickSort(ss []int, begin int, end int) {
	if begin+1 < end {
		mid := partition(ss, begin, end)
		quickSort(ss, begin, mid)
		quickSort(ss, mid+1, end)
	}
}

func quickSortV2(arr []int, l, r int) {
	if l < r {
		key := arr[(l+r)/2]
		i := l
		j := r
		for {
			for arr[i] < key {
				i++
			}
			for arr[j] > key {
				j--
			}
			if i >= j {
				break
			}
			arr[i], arr[j] = arr[j], arr[i]
		}
		quickSortV2(arr, l, i-1)
		quickSortV2(arr, i+1, r)
	}
}

func RunQuickSort() {
	fmt.Println("运行算法题，快速排序！！！")
	// wg.Add(1)
	ss := []int{5, 4, 3, 2, 1}
	fmt.Println(map[string]interface{}{
		"初始数组": ss,
	})
	quickSort(ss, 0, 5)
	fmt.Println(map[string]interface{}{
		"快排后的数组": ss,
	})
	// wg.Done()
	quickSortV2(ss, 0, len(ss)-1)
	fmt.Println(map[string]interface{}{
		"快排后的数组": ss,
	})
}
